#define _CRT_SECURE_NO_WARNINGS 2

#include<iostream>
#include<string.h>
using namespace std;

void get_next(char* s1,int* next, int n) {
	int i = 0;
	int j = 0;
	next[0] = 0;
	while (j < n) {
		if (i == 0 || s1[i] == s1[j]) {
			if (i)
			{
				i++;
			}
			j++;
			next[j] = i;
		}
		else {
			i = next[i];
		}
	}
	for (int k = 0; k < n; k++) {
		cout << next[k] << " ";
	}
}

void kmp(const char* s1,const char* s2,int* next) {
	int i = 0;
	int j = 0;
	while (i < (int)strlen(s1) && j < (int)strlen(s2)) {
		if (j==0||s1[i] == s2[j]) {
			if (j ) {
				j++;
			}
			i++;
		}
		else {
			j = next[j];
		}
	}
	if (j == (int)strlen(s2) ) {
		cout <<endl<<"find" << endl;
	}
	else {
		cout << "not find" << endl;
	}
}


int main() {
	/*char s[] = "asfsdfd";
	int arr[] = { 1,2,3 };*/
	 
	char s1[30] = { 0 }, s2[30] = { 0 };
	cout << "please input the s1 string" << endl;
	cin >> s1;
	
	cout << "please input the s2 string" << endl;
	cin >> s2;
	int len = strlen(s2);
	int next[20] = { 0 };
	get_next(s2,next, len);
	kmp(s1, s2, next);
	return 0;
}